package sword;

/**
 * 题目：在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，
 * 每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
 * @author longzj
 */
public class FindNumInSortedArray {

    private static final int VALID = -1;
    private static final int INVALID = -2;
    private static final int NEXT = -3;

    public static void main(String[] args) {
        FindNumInSortedArray array = new FindNumInSortedArray();
        int[][] testSource = new int[][]{
                {1, 2, 2, 4},
                {2, 3, 4, 5},
                {4, 8, 16, 23},
                {6, 9, 34, 48},
        };

        int[] testArray = new int[]{
                1, 16, 48, 34
        };
        for (int value : testArray) {
            System.out.println(value + " is in array ?: " + array.find(value, testSource));
        }
    }

    private boolean find(int num, int[][] array) {
        return array.length != 0 && check(num, array, array[0].length, 0);
    }


    /**
     * 递归确认数字是否出现在二维数组中<br>
     * 因为二维数组是横纵非递减的，首先判断数字在一个一维数组的大小位置，减少比较，最后逐步缩小范围;
     *
     * @param num       需要判断的数
     * @param array     二维数组
     * @param lineIndex 需比较的一维数组最尾部位置
     * @param rowIndex  比较的行位置
     * @return 二维数组中是否存在数字
     */
    private boolean check(int num, int[][] array, int lineIndex, int rowIndex) {
        for (int i = rowIndex; i < array.length; i++) {
            rowIndex = i;
            int[] row = array[i];
            int tmp = lineIndex;
            lineIndex = checkInternal(num, row, lineIndex);
            if (lineIndex == VALID) {
                return true;
            } else if (lineIndex == INVALID) {
                return false;
            } else if (lineIndex >= 0) {
                return check(num, array, lineIndex, rowIndex);
            } else if (lineIndex == NEXT) {
                lineIndex = tmp;
            }
        }

        return false;
    }

    /**
     * 判断数字是否存在于此一维数组中，或者大小是否在此数组范围内
     *
     * @param num    需要判断的数字
     * @param array  一维数组
     * @param endPos 需比较的一维数组最尾部位置
     * @return 返回值如下几种：<br>
     * <li>VALID : 数字在当前数组内
     * <li>INVALID ：数字不在在当前数组内
     * <li>NEXT  ：数字大于当前数组的所有值
     * <li>具体数值：数字在当前数组范围内，比具体数值+1对应的数组内容小
     */
    private int checkInternal(int num, int[] array, int endPos) {

        if (endPos <= 0 || array.length == 0) {
            return INVALID;
        }
        int leftNum = array[0];
        if (num < leftNum) {
            return INVALID;
        }
        int rightNum = array[endPos - 1];
        if (num > rightNum) {
            return NEXT;
        }

        if (num == leftNum || num == rightNum) {
            return VALID;
        }

        int leftIndex = 0;
        int rightIndex = endPos;

        while (true) {
            endPos = rightIndex - leftIndex;
            int mid = endPos / 2;
            if (mid == 0) {
                return leftIndex;
            }
            mid += leftIndex;
            int value = array[mid];
            if (num < value) {
                rightIndex = mid;
            } else if (num > value) {
                leftIndex = mid;
            } else {
                return VALID;
            }
        }

    }

}
